/**
 * 快速排序
 * 基本思想
 * 我们从数组中选择一个元素为中轴元素，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边
 * 从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，
 * 接着通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。
 * 
 * 具体步骤：
 * 1.从数列中挑出一个元素，称为 “基准”（pivot）;
 * 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
 *     在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 * 3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
 * 
 * 最好时间复杂度：O(NlogN)
 * 最坏时间复杂度：O(N^2)
 * 最坏时间复杂度：O(NlgN)
 * 空间复杂度：O(logN)
 * 
 * 稳定排序：否
 * 原地排序：是
*/
#include "../../include/common.h"


int *quick_sort(Node* pBegin, Node* pEnd) {
    if(pBegin == NULL || pEnd == NULL || pBegin == pEnd)
        return 0;
    //定义两个指针
    Node* p1 = pBegin;
    Node* p2 = pBegin->next;
    int pivot = pBegin->data;

    //每次只比较小的，把小的放在前面。经过一轮比较后，被分成左右两部分。其中p1指向中值处，pbegin 为 pivot。
    while(p2 != NULL) { /* && p2 != pEnd->next */
        if(p2->data < pivot) {
            p1 = p1->next;
            if(p1 != p2) {
                SwapData(&p1->data, &p2->data);
            }
        }
        p2 = p2->next;
    }
    /*此时pivot并不在中间，我们要把他放到中间，以他为基准，把数据分为左右两边*/
    SwapData(&p1->data, &pBegin->data);
    //此时p1是中值节点
    //if(p1->data >pBegin->data)
    quick_sort(pBegin, p1);
    //if(p1->data < pEnd->data)
    quick_sort(p1->next, pEnd);
}


/**
 * 改进方案：
 * 1. 选取随机数作为枢轴。
 *     但是随机数的生成本身是一种代价，根本减少不了算法其余部分的平均运行时间。
 * 2. 使用左端，右端和中心的中值做为枢轴元。
 *     经验得知，选取左端，右端，中心元素的中值会减少了快排大约*14%的比较。
 * 3. 每次选取数据集中的中位数做枢轴。
 *     选取中位数的可以在 O(n)时间内完成。（证明见《算法导论（第二版） 》） P111 第九章：在平均情况下，任何顺序统计量（特别是中位数）都可以在线性时间内得到。
 * 4. 快速排序在处理小规模数据时的表现不好。这个时候可以改用插入排序。
 * 5. 对于一个每个元素都完全相同的一个序列来讲，快速排序也会退化到O(n^2)
 *     要将这种情况避免到，可以这样做：
 *         在分区的时候，将序列分为 3 堆，一堆小于中轴元素，一堆等于中轴元素，一堆大于中轴元素，
 *         下次递归调用快速排序的时候，只需对小于和大于中轴元素的两堆数据进行排序，中间等于中轴元素的一堆已经放好。
*/


/* ----------------------------------- */

int Partition(ElementType arr[], int low, int high){
    ElementType pivot = arr[low];
    while (low < high){ // 从首尾同时开始完成一次遍历
        // 从后往前寻找第一个小于 pivot 的元素
        while (low < high && arr[high] >= pivot)
            high--;
        arr[low] = arr[high];
        // 从前往后寻找第一个大于 pivot 的元素
        while (low < high && arr[low] <= pivot)
            low++;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

void QuickSort(ElementType arr[], int low, int high){
    if (low < high){
        int pivot = Partition(arr, low, high);
        QuickSort(arr, low, pivot-1);
        QuickSort(arr, pivot+1, high);
    }
}